perm filename PRO[1,DBL] blob
sn#064615 filedate 1973-10-01 generic text, type T, neo UTF8
00100
00200
00300 PROTOCOL FOR AUTOMATIC PROGRAM WRITING SYSTEM
00400 WRITING A CONCEPT-FORMATION PROGRAM
00500 (SIMILAR TO WINSTON'S PROGRAM)
00600
00100
00200 This protocol will be structured around the flow through the PUP
00300 system. Thus it will appear very similar to the ultimate QLISP-type
00400 trace. Function names appear as CAPITALS, and comments are in normal
00500 lower case. Indentation corresponds to function call depth; two spaces
00600 for each level.
00700
00800 SERVE
00900 This function is the starting point of the PUP system. Its name reflects
01000 the fundamental drive of any puppy: to serve its master. Serve sees that
01100 nothing is being done, and calls OBTAIN:USABLE:INFORMATION repeatedly,
01200 until the latter returns something which can be considered a task.
01300
01400 OBTAIN:USABLE:INFORMATION
01500 This function decides which of TRANSLATE, GET:NEW:INFORMATION,
01600 ANALYZE:IMPLICATIONS, and EXTRACT:RELEVANT:SUBSET
01700 to attempt in the present situation. It affects this by calling CHOOSEFROM.
01800
01900 CHOOSEFROM
02000 This function evaluates each possibility and picks the best one.
02100 It knows that when choosing among functions, we should examine the
02200 "when" part of each function description, to see how relevant it is.
02300 If some functions tie for tops here, we see how hard it would be to
02400 satisfy each's preconditions. If we still have a conflict, we pick
02500 the function easiest to implement usually.
02600 In our present vacuous situation, only GET:NEW:INFORMATION is relevant.
02700
02800 GET:NEW:INFORMATION
02900 This requires, as a precondition, that PUP know the specifics of
03000 what new information it wants.
03100
03200 SPECIFICS
03300 In our present case, this function is trivial, since PUP merely
03400 wants any type of command.
03500 end of SPECIFICS
03600
03700 Now GET:NEW:INFORMATION continues. It asks that a message be
03800 printed to the user, informing him of the specifics of what is wanted.
03900
04000 MESSAGE
04100 Prints out something like "PUP: I want any task"
04200 end of MESSAGE
04300
04400 Pup now reads in what info. was requested. Assertions, to the
04500 effect that we have some new information, are made.
04600 end of GET:NEW:INFORMATION
04700
04800 end of CHOOSE:FROM
04900
05000 end of OBTAIN:USABLE:INFORMATION
05100
05200 We are now back in Serve. Suppose the user has typed in:
05300 "Write a program which does concept formation"
05400 This is our new information. We test to see if it is executable;
05500 that is, whether ∃ function named WRITE which can meaningfully
05600 take the six arguments a, program, which, does, concept, formation.
05700 This of course fails, so we repeat OBTAIN:USABLE:INFORMATION.
05800
05900 OBTAIN:USABLE:INFORMATION
06000 Once again, we choose from the four possible functions.
06100
06200 CHOOSE:FROM
06300 Since new information exists, GET:NEW:INFORMATION is no longer
06400 the ideal choice. This time, TRANSLATE wins.
06500
06600 TRANSLATE
06700 This is accomplished by breaking the info. up into a few pieces,
06800 and looking each piece up in our dictionary. If it were done in a
06900 better way, I would call it parsing. The crude mechanism is to
07000 backtrack until we succeed or else until all possible break-ups have
07100 been tried.
07200
07300 PARSE
07400 This (eventually) breaks the info. into
07500 (write a program which does) (concept formation).
07600 end of PARSE
07700
07800 LOOKUP
07900 Recognizes (write a program which does) as a call to the
08000 known system function WRITE:PROGRAM.
08100 end of LOOKUP
08200
08300 LOOKUP
08400 Recognizes (concept formation) as the subject CONCEPT:FORMATION.
08500 For uniformity, all topics are built in as procedures. So this is just
08600 a call to the function called CONCEPT:FORMATION.
08700 end of LOOKUP
08800
08900 Translate now examines EXTRACT:RELEVANT:SUBSET, to see whether
09000 or not to apply that function to the translated information. But this
09100 isn't applicable unless the information is very large in size, which
09200 it is not. As a post-requisite, Translate sees whether the translated
09300 information is usable as it is. If not, it may call itself recursively.
09400 But (WRITE:PROGRAM (CONCEPT:FORMATION)) is usable, so we are done.
09500 end of TRANSLATE
09600
09700 end of CHOOSE:FROM
09800
09900 end of OBTAIN:USABLE:INFORMATION
10000
10100 Serve again examines the information. This time, it is executable,
10200 so its final action is to execute the information.
10300
10400 WRITE:PROGRAM
10500 This function is now called, with the task it is to do (its argument)
10600 set to CONCEPT:FORMATION. We check that the ability to do the task does
10700 not already exist. Then we get the name the user wishes to call the
10800 program.
10900
11000 GET:NAME
11100 The first step, since PUP is smart, is to generate a set of plausible
11200 names for the task.
11300
11400 PLAUSIBLE:NAMES
11500 From CONCEPT:FORMATION we generate the plausible names
11600 using initials, mainwords, firstfew, and compositions of the
11700 preceding. In this case: CF, C, CONCEPT:FORMATION, CONCEPT.
11800 Next we eliminate all previously-known identifiers from this list.
11900 Say CONCEPT:FORMATION is in our dictionary, and C is a known constant.
12000 We thus return the two names CF and CONCEPT.
12100 end of PLAUSIBLE:NAMES
12200
12300 The second precondition for GET:NAME is that the user be aware of
12400 the plausible names for the task. PUP searches its list of functions
12500 for one which makes the user aware of some given fact.
12600
12700 MESSAGE
12800 We print something like "The plausible names for the task
12900 (CONCEPT:FORMATION) are CF and CONCEPT."
13000 end of MESSAGE
13100
13200 Pup now begins to execute GET:NAME proper. First a note is printed.
13300
13400 MESSAGE
13500 Prints "What does user wish to call the task (CONCEPT:FORMATION)?"
13600 end of MESSAGE
13700
13800 Next GET:NAME reads in the user's reply. Say the user types
13900 "CF". We then assert that PUP and the user may now refer to the
14000 task as CF. That is, the name of the program PUP is going to write
14100 is CF.
14200 end of GET:NAME
14300
14400 The next prerequisite of WRITE:PROGRAM is now satisfied:
14500
14600 MESSAGE
14700 Prints "PUP: I am ready to begin to write CF program to do
14800 CONCEPT:FORMATION."
14900 end of MESSAGE
15000
15100 The final prerequisite to WRITE:PROGRAM is that Pup investigate
15200 the type of the task. In this case, we must see what types of concept
15300 formation there are, and how -- and when -- we decide the particular
15400 type(s) the user wants CF to handle.
15500
15600 TYPE
15700 In the dictionary, under CONCEPT:FORMATION, there is a category
15800 of facts about type. To preserve uniformity, these are structured as
15900 a set of procedural decisions. This is perhaps equivalent to a
16000 discrimination net. Each decision which must (eventually) be made is
16100 asserted as such. Effects, and when the decision must be made, are
16200 provided for most of these. The list we find is something like:
16300 (1) Concept formation can be done at one of three levels of sophistocation:
16400 (a) Classificatory
16500 (b) Comparitive
16600 (c) Metrical
16700
16800 (2) Concepts may vary with time
16900 Affected: The basic structure of forming a concept
17000
17100 (3) Concept formation may be dependent upon the speed of presentation
17200 of stimuli.
17300 Affected: Amount of effort expended on identification of stimulus.
17400
17500 (4) Instances may be left in view indefinitely or removed after processing.
17600 Affected: Whether new relations can be derived as needed, or
17700 all relations must be derived upon initial exposure to
17800 the stimulus.
17900 When: Before deciding firmly how to get relations from input stimulus.
18000
18100 (5) Logical complexity of the correct concept specification may vary,
18200 from purely conjunctive concepts to purely disjunctive concepts
18300 to mixed expressions.
18400 Affected: How we store the description of a concept.
18500
18600 (6) Positive transfer, negative transfer, neither, or both,
18700 may be present.
18800 Affected: How previous concepts learned and previous stimuli effect
18900 learning of new concept and recognition that it is new.
19000 When: Before we decide firmly how to search through our set of concepts
19100 and before we decide firmly how to insert a new concept into our
19200 set of concepts.
19300
19400 (7) Positive instances, negative instances, or both may be present.
19500 Affected: Whether to use {positive, negative} information to modify
19600 the description of a concept.
19700
19800 (8) Subject-specific behavior may be required.
19900 Affected: Parameters describing an individual must be read in.
20000 When: Before any processing routines are finalized.
20100 Why: Any processing routine might have to depend upon some parameters.
20200
20300 (9) Precise types of desired subject responses must be decided.
20400 Affected: Output variables, output format.
20500
20600 Co-requisite with the writing of the program, a new context is
20700 created, and named WRITE:CF:PROGRAM.
20800 The main part of WRITE:PROGRAM begins. We repeatedly do the
20900 following: pick the best function from {OBTAIN:USABLE:INFORMATION,
21000 USE:INFORMATION, FILL:IN:UNDEFINED:SECTION, CLARIFY:IMPROBABLE:SITUATION,
21100 FIX:INCORRECT:PIECE} and execute it. Repeatedly means `until done'
21200 which in this case means until the assertion (COMPLETED CF) exists.
21300 The heart of `repeatedly' is just a loop continually calling CHOOSE:FROM.
21400
21500 REPEATEDLY
21600 (CHOOSE:FROM)
21700 In our current situation, usable new information is present. We
21800 have no need for more of it yet, and we have no undefined, improbable,
21900 or incorrect pieces of code, since no code has even been generated yet.
22000 So our choice is easy.
22100
22200 USE:INFORMATION
22300 Again, this function merely chooses the best function from a set
22400 and then executes it. In this case the possibilities are
22500 {DECOMPOSE, DEFER:TASK, DEFER:DECISION, CHOOSE:DATA:STRUCTURE,
22600 CHOOSE:ALGORITHM, ENCODE, COMMENT}. Each will be used eventually, so
22700 don't worry now about all of them. Pup is happiest about deferring,
22800 and it finds several decisions exist already. The way is clear.
22900
23000 DEFER:DECISION
23100 As a precondition, Pup must have some knowledge of when we must
23200 next reinvestigate this decision. Some of the decisions which were
23300 set up by deciding that the task was CONCEPT:FORMATION have explicit
23400 information regarding when they must be made. Most of the decisions'
23500 when parts can be trivially obtained by prefacing the Affected part
23600 by the word "BEFORE", and following it by the words "IS FIRMLY DECIDED".
23700 The remainder of the decisions require some use of programming knowledge
23800 and concept formation knowledge to decide when they can be deferred to.
23900 When a decision can no longer be deferred (either because it actually
24000 must be made now, or because the system isn't smart enough to figure out
24100 how long it can put it off) the decision is actually made. This will
24200 usually require asking the user, but sometimes knowledge gleaned in the
24300 preceding activity will settle the decision. This is the whole motivation
24400 for trying to defer a decision as long as possible.
24500 Okay; now we get down to details. Suppose this call to DEFER:DECISION
24600 we are trying to stall decision (1), that is, whether the level of
24700 concept formation is classificatory, comparitive, or metrical.
24800 No when part is provided; in fact, no affected part is provided.
24900 At this point, the prerequisite of DEFER:DECISION sets up the subgoal
25000 that Pup find out when (that is, in what situation) it must next
25100 reinvestigate this decision.
25200
25300 WHEN:NEXT
25400 The prerequisite of knowing when next to worry about the decision
25500 is to understand the effects of (the alternatives of) the decision.
25600 In our case, we identify the alternatives as the three levels. Each of
25700 these is a separate entry in our dictionary, hence a known function.
25800 Understanding the effects means retrieving the effects part of each.
25900 For CLASSIFICATORY:CONCEPT:FORMATION this is something like
26000 "partition a domain".
26100 For COMPARITIVE:CONCEPT:FORMATION this is like
26200 "partition a domain, then linearly order the equivalence classes".
26300 For METRICAL:CONCEPT:FORMATION this is something like
26400 "partition a domain, then linearly order the equivalence classes,
26500 then define a meaningful way of joining elements of the domain,
26600 then determine an absolute scale on the domain that satisfies:
26700 the scale values of two elements is equal iff they are in the same
26800 class; the scale value of one element is less than the scale
26900 value of a second iff the class of the first is less than the class
27000 of the second according to the linear ordering of classes; the
27100 scale value of the join of two elements equals the sum of the scale
27200 values of the two elements".
27300
27400 Now that Pup understands the effects of the alternatives, it begins
27500 to execute WHEN:NEXT proper. This is merely a call to use programming
27600 knowledge about decision-deferring, applied to the effects, to determine
27700 the situation when Pup must differentiate between the alternatives.
27800
27900 One piece of programming knowledge says that "if we must decide
28000 between alternatives in set X, then we may defer the decision until
28100 after accomplishing (SETINTERSECTION (MAPCAR X PROCEDURE)), that is,
28200 until after we have done the things that must be done regardless of
28300 the outcome of the decision.
28400 In our case, we find we can apply this bit of knowledge; it tells us
28500 to first get "partition a domain" completed, then worry about what
28600 level CF must handle. We examine the piece of advice more extensively
28700 now, and see it has a suggestion: code the current task now, with
28800 the set-intersection as one subfunction call. Later, other parts
28900 of the set-union of the effects may have to be added, and we can make
29000 a note of that right now.
29100 Pup thus gets the next situation to worry about level: when
29200 (partition a domain) has been completed.
29300 end of WHEN:NEXT
29400
29500 We now execute the main part of DEFER:DECISION, which is to
29600 demonize that situation. We assume that demonizing is primitive.
29700 end of DEFER:DECISION
29800